package 链表;

import java.util.HashMap;
import java.util.Map;

/**
 *146. LRU 缓存
   * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
    解题思路：
    LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，当缓存达到容量上限时，它会优先淘汰最近最少使用的数据。为了实现LRU缓存，我们需要一个数据结构来支持以下操作：

 */
public class L_146_1 {

    private DLinkedNode head,tail; // 维护一个双端链表
    private Map<Integer,DLinkedNode> cache; // 通过index作为key，用于快速查找链表节点的位置
    private int size; // 当前链表的实际长度
    private int capacity; // 该缓存的容量

    public L_146_1(int capacity) {
        this.cache = new HashMap<>();
        this.capacity = capacity;
        this.size = 0;

        // 定义首位辅助节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 根据缓存下标快速查找节点，如果查找到，就将该节点移动到链表头部
     * @param key
     * @return
     */
    public int get(int key) {
        DLinkedNode dLinkedNode = cache.get(key);
        if (dLinkedNode == null){
            return -1;
        }
        // 移动至头结点
        moveToHead(dLinkedNode);
        return dLinkedNode.value;
    }

    /**
     * 先在cache中查询在不在
     *  如果不在，就创建一个新节点，并添加到链表头部，同时更新缓存 （需要判断当前缓存的大小有没有超过容量值）
     *  如果在，就将已经存在的这个节点移动到链表头部
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        DLinkedNode dLinkedNode = cache.get(key);
        // 如果没有找到，需要创建一个新节点添加，但是需要判断当前缓存的大小情况
        if (dLinkedNode == null){
            // 先添加当前节点到头结点，然后判断是否超过缓存容量大小
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            cache.put(key,newNode);
            size++;
            // 如果当前容量的大小超过缓存大小，就移除尾部节点
            if (size > capacity){
                // 移除链表的尾部节点
                DLinkedNode removedTail = removeTail();
                // 移除map中的缓存
                cache.remove(removedTail.key);
                size--;
            }

        }else {
            // 将原来的节点更新值后，移动到头结点
            dLinkedNode.value = value;
            moveToHead(dLinkedNode);
        }
    }

    // 定义双向链表节点
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    // 添加节点到链表头部
    private void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 移除节点, 找到当前节点的前驱节点与后继节点
    private void removeNode(DLinkedNode node){
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    /**
     * 将节点移动到链表头部
     * @param node
     */
    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }

    // 移除链表尾部的节点
    private DLinkedNode removeTail(){
        // 找到尾结点tail的前驱节点，然后移除
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
